template <class T>
class BIT
{
    int n;
    vector<T> tr, tr1;

public:
    BIT(T _n) : tr(_n + 10, 0), tr1(_n + 10, 0), n(_n) {}
    int lowbit(int x)
    {
        return x & (-x);
    }
    void add(T x, T w)
    {
        int w1 = x * w;
        for (int i = x; i <= n; i += lowbit(i))
        {
            tr[i] += w;
            tr1[i] += w1;
        }
    }
    void add(int l, int r, int w)
    {
        add(l, w);
        add(r + 1, -w);
    }
    int sum(vector<int> &t, int k)
    {
        int ret = 0;
        while (k)
        {
            ret += t[k];
            k -= lowbit(k);
        }
        return ret;
    }
    int sum(int l, int r)
    {
        return (r + 1ll) * sum(tr, r) - 1ll * l * sum(tr, l - 1) - (sum(tr1, r) - sum(tr1, l - 1));
    }
};
// 树状数组区间加，使用add(l,r,x)